343D - Water Tree - CodeForces Solution

// Problem: D. Water Tree
// Contest: Codeforces - Codeforces Round 200 (Div. 1)
// URL: https://codeforces.com/problemset/problem/343/D
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define F first
#define S second
#define sl "\n"
using namespace std;
using ll=long long;
using ii=pair<long long,long long>;
using vi=vector<int>;
const int N=5e5+5;
int n,q;
vector<int> g[N];
set<int> s[N];
vector<int> p[N],k[N];
bool vs[N];
int ans[N];
vector<int> an;
set<int>ss;
set<int>& dfs(int u) {
	vs[u]=1;
	auto& adios=s[u];
	for (int w : p[u]) ss.insert(w);
	for (int v : g[u]) if (!vs[v]) {
		auto &hola=dfs(v);
		if (adios.size() < hola.size()) swap(adios,hola);
		
		for (int w : hola) adios.insert(w); 
	}
	for (int w : k[u]) {
		// let x the greatest index that appears in s[u][1] that is less than w
		// let y the greatest index that appears in s[u][2] that is less than w
		// if x < y then i am empty
		// otherwise im not
		auto x=ss.lower_bound(w);
		auto y=adios.lower_bound(w);
		if (x==ss.begin()) ans[w]=0;
		else {
			if (y==adios.begin()) {
				ans[w]=1;
			}	 else {
				x--;
				y--;
				if ((*x)<(*y)) {
					ans[w]=0;
				} else {
					ans[w]=1;
				}
			}
		}
		
	}
	for (int w : p[u]) ss.erase(ss.find(w));
	return adios;
}
void solve() {
    cin>>n;


    for (int i=1;i<n;i++) {
    	int u,v;
    	cin>>u>>v;
    	g[u].push_back(v);
    	g[v].push_back(u);
    } 
    cin>>q;
    for (int i=1;i<=q;i++) {
    	int t,x;
    	cin>>t>>x;
    	if(t==1) {
    		p[x].push_back(i);
    	} else if (t==2) {
    	s[x].insert(i);
    	} else {
    		k[x].push_back(i);
    	}
    	if (t==3) {
    		an.push_back(i);
    	}
    }

    dfs(1);
    for (int u : an) cout<<ans[u]<<"\n";
}
int main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    /* int t;cin>>t;while(t--)*/
    solve();
    return 0;
}